#include "MovieCollection.h"
#include <iostream>

using namespace std;

MovieCollection::MovieCollection(void) : root(NULL) {

}

MovieCollection::~MovieCollection(void) {

}

void MovieCollection::addMovie(Movie *item) {
	// adds a movie to the tree
	Movie* itemPointer = new Movie;
	itemPointer = item;
	Movie* parent;

	itemPointer->setLeft(NULL); // sets left child
	itemPointer->setRight(NULL); // sets right child

	// check if it is a new tree
	if(isEmpty()) {
		root = itemPointer;
	} else {
		// determines that it is a leaf node
		Movie* current;
		current = root;
		// find the Node's parent
		while(current) {
			parent = current;
			if(itemPointer->getMovieBinaryId() > current->getMovieBinaryId()) current = current->getRight();
			else current = current->getLeft();
		}

		if(itemPointer->getMovieBinaryId() < parent->getMovieBinaryId()) {
			parent->setLeft(itemPointer);
		} else {
			parent->setRight(itemPointer);
		}
	}
}

void MovieCollection::printInAlphabeticalOrder() {
	// first reset counter
	positionCounter = 0;

	printInAlphabeticalOrder(root);
}

void MovieCollection::printInAlphabeticalOrder(Movie* item) {
	if(item != NULL) {
		if(item->getLeft()) printInAlphabeticalOrder(item->getLeft());

		// increment count for numbers 1 to x to align
		positionCounter++;

		// figure out the number of dvds in store
		int numberOfDvdsInStore = numberOfDvdsInStoreForAMovie(item);
		cout <<"\t" << positionCounter << ") " << item->getTitle() << " ~ " << 
			item->getStarring() << " : " << numberOfDvdsInStore << " in store" << endl;

		if(item->getRight()) printInAlphabeticalOrder(item->getRight());
	}
}

int MovieCollection::sizeOfMovieCollection(Movie* item) { 
	// returns the size of the tree
	if (item == NULL) return 0;
	return 1 + max (sizeOfMovieCollection (item->getLeft()), sizeOfMovieCollection (item->getRight())); 

}

void MovieCollection::printAllRentedMovies(string userName) {
	// first reset counter
	positionCounter = 0;

	printAllRentedMovies(root, userName);
}

void MovieCollection::printAllRentedMovies(Movie* item, string userName) {
	if(item != NULL) {
		if(item->getLeft()) printAllRentedMovies(item->getLeft(), userName);

		// increment count for numbers 1 to x to align
		positionCounter++;

		int numberOfDvdsInStore = numberOfDvdsInStoreForAMovie(item);
		for (int dvdNumber = 0; dvdNumber < item->dvdCount(); dvdNumber++) {
			Dvd* retrievedDvd = item->retrieveDvd(dvdNumber);
			if (retrievedDvd->isRented && retrievedDvd->rentedBy == userName) {
				cout <<"\t" << positionCounter << ") " << item->getTitle() << endl;
			}
		}

		if(item->getRight()) printAllRentedMovies(item->getRight(), userName);
	}
}

bool MovieCollection::checkUserRentals(std::string userName) {
	if (checkUserRentals(root, userName)) {
		return true;
	} else {
		return false;
	}
}

bool MovieCollection::checkUserRentals(Movie* item, string userName) {
	// check if user has rentals
	if(item != NULL) {
		if(item->getLeft()) checkUserRentals(item->getLeft(), userName);

		int numberOfDvdsInStore = numberOfDvdsInStoreForAMovie(item);
		for (int dvdNumber = 0; dvdNumber < item->dvdCount(); dvdNumber++) {
			Dvd* retrievedDvd = item->retrieveDvd(dvdNumber);
			if (retrievedDvd->isRented && retrievedDvd->rentedBy == userName) {
				return true; // returns true if user does have rentals
				break;
			} else {
				return false; // return false if user is clean
				break;
			}
		}

		if(item->getRight()) checkUserRentals(item->getRight(), userName);
	}
}

void MovieCollection::getRentersOfMovie(Movie* item) {
	if(item != NULL) {
		if(item->getLeft()) getRentersOfMovie(item->getLeft());

		// increment count for numbers 1 to x to align
		positionCounter++;

		int numberOfDvdsInStore = numberOfDvdsInStoreForAMovie(item);
		for (int dvdNumber = 0; dvdNumber < item->dvdCount(); dvdNumber++) {
			Dvd* retrievedDvd = item->retrieveDvd(dvdNumber);
			if (retrievedDvd->isRented) { // checks if the movie in the tree is rented by this user
				cout <<"\t" << dvdNumber + 1 << ") " << item->getTitle() << " rented by " << retrievedDvd->rentedBy << endl;
			}
		}

		if(item->getRight()) getRentersOfMovie(item->getRight());
	}

}

int MovieCollection::searchByTitle(std::string movieTitle) {
	// first reset counter
	positionCounter = 0;

	searchByTitle(movieTitle, root);

	return positionCounter;
}

void MovieCollection::searchByTitle(std::string movieTitle, Movie* item) {
	if(item != NULL) {
		if(item->getLeft()) searchByTitle(movieTitle, item->getLeft());

		// see if the text is in the title
		size_t found;
		found = item->getTitle().find(movieTitle);
		if (found!=string::npos) {
			// increment count for numbers 1 to x to align
			positionCounter++;

			// figure out the number of dvds in store
			int numberOfDvdsInStore = numberOfDvdsInStoreForAMovie(item);
			cout<<"\t" << positionCounter << ") " << item->getTitle() << " ~ " << 
				item->getStarring() << " : " << numberOfDvdsInStore << " in store" << endl;
		}

		if(item->getRight()) searchByTitle(movieTitle, item->getRight());
	}
}

int MovieCollection::searchByUser(std::string movieTitle, std::string userName) {
	// first reset counter
	positionCounter = 0;

	searchByUser(movieTitle, root, userName);

	return positionCounter;
}

void MovieCollection::searchByUser(std::string movieTitle, Movie* item, std::string userName) {
	if(item != NULL) {
		if(item->getLeft()) searchByUser(movieTitle, item->getLeft(), userName);

		// see if the text is in the title
		size_t found;
		found = item->getTitle().find(movieTitle);
		if (found!=string::npos) {

			// figure out the number of dvds in store
			int numberOfDvdsInStore = numberOfDvdsInStoreForAMovie(item);
			for (int dvdNumber = 0; dvdNumber < item->dvdCount(); dvdNumber++) {
				Dvd* retrievedDvd = item->retrieveDvd(dvdNumber);
				if (retrievedDvd->rentedBy == userName) {
					// increment count for numbers 1 to x to align
					positionCounter++;
					cout<<"\t" << positionCounter << ") " << item->getTitle() << endl;
				}
			}
		}
	}
	if(item->getRight()) searchByUser(movieTitle, item->getRight(), userName);
}

Movie *MovieCollection::searchByTitleChoice(std::string movieTitle, int choicePosition) {
	// first reset counter
	positionCounter = 0;

	searchByTitleChoice(movieTitle, choicePosition, root);

	return movieChoice;
}

void MovieCollection::searchByTitleChoice(std::string movieTitle, int choicePosition, Movie* item) {
	if(item != NULL) {
		if(item->getLeft()) searchByTitleChoice(movieTitle, choicePosition, item->getLeft());

		// see if the text is in the title
		size_t found;
		found = item->getTitle().find(movieTitle);
		if (found!=string::npos) {
			// increment count for numbers 1 to x to align
			positionCounter++;

			// return the correct choice
			if (positionCounter == choicePosition) {
				movieChoice = item;
			}
		}

		if(item->getRight()) searchByTitleChoice(movieTitle, choicePosition, item->getRight());
	}
}

bool MovieCollection::isEmpty() const {
	if (root == NULL) {
		return true;
	} else {
		return false;
	}
}

int MovieCollection::numberOfDvdsInStoreForAMovie(Movie* item) {
	int numberOfDvdsInStore = 0;
	// loop through each dvd and if isRented is false increment count
	for (int dvdNumber = 0; dvdNumber < item->dvdCount(); dvdNumber++) {
		Dvd* retrievedDvd = item->retrieveDvd(dvdNumber);
		if (!retrievedDvd->isRented) {
			numberOfDvdsInStore++;
		}
	}
	return numberOfDvdsInStore;
}

int MovieCollection::numberOfDvdsOutOfStoreForAMovie(Movie* item) {
	int numberOfDvdsOutOfStore = 0;
	// loop through each dvd and if isRented is false increment count
	for (int dvdNumber = 0; dvdNumber < item->dvdCount(); dvdNumber++) {
		Dvd* retrievedDvd = item->retrieveDvd(dvdNumber);
		if (retrievedDvd->isRented) {
			numberOfDvdsOutOfStore++;
		}
	}
	return numberOfDvdsOutOfStore;
}

void MovieCollection::deleteMovie(std::string movieBinaryId) {
	//Locate the element
	bool found = false;
	bool isRoot = false;
	bool firstCheck = true;
	if (isEmpty()) {
		cout<<" This Tree is empty! "<<endl;
		return;
	}

	Movie* thisMovie;
	Movie* parent;
	thisMovie = root;

	while (thisMovie != NULL) {
		// if the root is the thing we are searching for
		if (thisMovie->getMovieBinaryId() == movieBinaryId) {
			found = true;
			// if its root set is root to true, else isRoot stays false
			if (firstCheck) {
				isRoot = true;
			}
			break;
		} else {
			// it will need to loop a second time at least
			firstCheck = false;
			// make the parent to be root
			parent = thisMovie;
			// if what we're looking for is larger than the root, move right
			if (movieBinaryId > thisMovie->getMovieBinaryId()) {
				thisMovie = thisMovie->getRight();
			} else {
				// else move left
				thisMovie = thisMovie->getLeft();
			}
		}
	}

	// if you can't find the data (ie go through the whole thing and it's not there)
	if (!found) {
		cout << "Data not found!" << endl;
	} else {
		// right now "thisMovie" is the movie we are deleting (or rather detaching)

		// go through the cases and deal with each

		// In the case of a leaf node (ie: no childeren)
		if (thisMovie->getLeft() == NULL && thisMovie->getRight() == NULL) {
			if (isRoot) {
				// close binary tree
				root = NULL;
			} else {
				// if the movie is to the left of the parent
				if (parent->getLeft() == thisMovie) {
					// dettach movie by making left null
					parent->setLeft(NULL);
				} else {
					// else it's to the right so dettach movie by making right null
					parent->setRight(NULL);
				}
			}
		} else if ((thisMovie->getLeft() == NULL && thisMovie->getRight() != NULL)|| 
			(thisMovie->getLeft() != NULL && thisMovie->getRight() == NULL)) {
				// Node with single child
				// if there's only one child either left or right

				// first deal with it if the child is attached on the right
				if (thisMovie->getLeft() == NULL && thisMovie->getRight() != NULL) {
					if (isRoot) {
						// then the child becomes the root
						root = thisMovie->getRight();
					} else {
						// if to the left of the parent is this movie
						if (parent->getLeft() == thisMovie) {
							// then attach the child on the right to the parent on the left
							parent->setLeft(thisMovie->getRight());
						} else {
							// attach the child on the right to the parent on the right
							parent->setRight(thisMovie->getRight());
						}
					}
				} else {
					// the child is on the left
					if (isRoot) {
						// then the child becomes the root
						root = thisMovie->getLeft();
					} else {
						// if the movie is to the left of the parent
						if (parent->getLeft() == thisMovie)
						{
							// then attach the child on the left to the parent on the left
							parent->setLeft(thisMovie->getLeft());
						} else {
							// then attach the child on the left to the parent on the right
							parent->setRight(thisMovie->getLeft());
						}
					}
				}
		} else if (thisMovie->getLeft() != NULL && thisMovie->getRight() != NULL) {
			// the movie has a child on the left and the right

			Movie* checkRight;
			checkRight = thisMovie->getRight();
			// first check if the right child is a leaf
			if((checkRight->getLeft() == NULL) && (checkRight->getRight() == NULL)) {
				// if it is then replace the movie with the right, making sure right is null
				checkRight->setLeft(thisMovie->getLeft());
				if (isRoot) {
					root = checkRight;
				} else {
					// check which side the movie is on and set checkRight to it
					if (parent->getRight() == thisMovie) {
						parent->setRight(checkRight);
					} else {
						parent->setLeft(checkRight);
					}
				}
			} else {
				//if the node's right child has a left child
				if(checkRight->getLeft() != NULL) {
					// then find the furthest left node (ie smallest before the right node)
					Movie* currentLeft;
					currentLeft = checkRight->getLeft();

					// loop and find the furthest left
					while(currentLeft->getLeft() != NULL) {
						// as you go keep shifting the left movie left
						checkRight = currentLeft;
						currentLeft = currentLeft->getLeft();
					}

					// great out of the loop, now current left if the 
					// smallest value right of the movie

					// if there are nodes to the right of the furthest left
					// then after the currentLeft is set to thisMovie
					// we need to set the right of furthest right to just right of this Movie
					if (currentLeft->getRight() != NULL) {
						// find furthest right
						Movie* currentRight;
						Movie* temporaryRight;
						temporaryRight = currentLeft;
						currentRight = temporaryRight->getRight();

						// loop and find the furthest right
						while(currentRight->getRight() != NULL) {
							// as you go keep shifting the left movie left
							temporaryRight = currentRight;
							currentRight = currentRight->getRight();
						}

						// now currentRight is the furthest right so attach
						// just right of thisMovie = the right leaf of furthest right
						currentRight->setRight(thisMovie->getRight());

						// now turn currentLeft into this movie (but don't set right)
						currentLeft->setLeft(thisMovie->getLeft());
						if (isRoot) {
							root = currentLeft;
						} else {
							// check which side the movie is on and set currentLeft to it
							if (parent->getRight() == thisMovie) {
								parent->setRight(currentLeft);
							} else {
								parent->setLeft(currentLeft);
							}
						}
					} else {
						// no right node (or left node) so
						// now turn currentLeft into this movie
						currentLeft->setLeft(thisMovie->getLeft());
						currentLeft->setRight(thisMovie->getRight());
						if (isRoot) {
							root = currentLeft;
						} else {
							// check which side the movie is on and set currentLeft to it
							if (parent->getRight() == thisMovie) {
								parent->setRight(currentLeft);
							} else {
								parent->setLeft(currentLeft);
							}
						}
					}

					// detach the current left from original position by making checkRight's left pointer null
					checkRight->setLeft(NULL);
				} else {
					// the rightCheck has no left node,
					// therefore the rightCheck is the smallest on the right
					// and has a right node; replace thisMovie with rightCheck
					checkRight->setLeft(thisMovie->getLeft());
					if (isRoot) {
						root = checkRight;
					} else {
						// check which side the movie is on and set checkRight to it
						if (parent->getRight() == thisMovie) {
							parent->setRight(checkRight);
						} else {
							parent->setLeft(checkRight);
						}
					}
				}
			}
		} // end many if statements
	} // end method
}

void MovieCollection::printTopTen() {
	// create 2 arrays to put data into, int and string
	int arraySize = sizeOfMovieCollection(root);
	int *rentalCounts;
	rentalCounts = new int[arraySize];
	int *movieIds;
	movieIds = new int[arraySize];
	int positionCount = 0;

	Movie* arrayMovie;
	// loop through movieCollections and get each movie and pop it into the arrays
	for (int movieNumber = 0; movieNumber < arraySize; movieNumber++) {
		arrayMovie = getMovieAtPosition(movieNumber);
		movieIds[movieNumber] = arrayMovie->getMovieId();
		rentalCounts[movieNumber] = arrayMovie->getRentalCount();
	}

	// sort arrays
	popularitySort(rentalCounts, movieIds, 0, arraySize - 1);

	// print top ten
	int topNumber;
	if (arraySize > 10)
		topNumber = 10;
	else
		topNumber = arraySize;
	for (int movieNumber = arraySize - 1; movieNumber >= 0; movieNumber--) {
		positionCount++;
		arrayMovie = getMovieById(movieIds[movieNumber]);
		cout << positionCount << ") " <<  arrayMovie->getTitle()
			<< " - popularity count: " << arrayMovie->getRentalCount() << endl;
	}

	// delete arrays
	delete [] rentalCounts;
	delete [] movieIds;
}

Movie *MovieCollection::getMovieAtPosition(int position) {
	// first reset counter
	positionCounter = 0;

	getMovieAtPosition(position, root);

	return movieChoice;
}

void MovieCollection::getMovieAtPosition(int position, Movie* item) {
	if(item != NULL) {
		if(item->getLeft()) getMovieAtPosition(position, item->getLeft());

		// return the correct choice
		if (positionCounter == position) {
			movieChoice = item;
		}

		// increment count for numbers 0 to x to align
		positionCounter++;

		if(item->getRight()) getMovieAtPosition(position, item->getRight());
	}
}

Movie *MovieCollection::getMovieById(int id) {
	getMovieById(id, root);

	return movieChoice;
}

void MovieCollection::getMovieById(int id, Movie* item) {
	if(item != NULL) {
		if(item->getLeft()) getMovieById(id, item->getLeft());

		// return the correct choice
		if (item->getMovieId() == id) {
			movieChoice = item;
		}

		if(item->getRight()) getMovieById(id, item->getRight());
	}
}

// sorts the array in order
void MovieCollection::popularitySort(int rentCountArray[], int movieIdArray[], int left, int right) {
	if (left < right) {
		int pivot = (left + right) / 2;
		int pivotNew = partition(rentCountArray, movieIdArray, left, right, pivot);
		popularitySort(rentCountArray, movieIdArray, left, pivotNew - 1);
		popularitySort(rentCountArray, movieIdArray, pivotNew + 1, right);
	}
}

// determines the parition of the array to sort
int MovieCollection::partition(int rentCountArray[], int movieIdArray[], int left, int right, int pivotIndex) {
	int pivot = rentCountArray[pivotIndex];
    do {
        while (rentCountArray[left] < pivot) left++;
        while (rentCountArray[right] > pivot) right--;
        if (left < right && rentCountArray[left] != rentCountArray[right])
        {
            swap(rentCountArray[left], rentCountArray[right]);
			swap(movieIdArray[left], movieIdArray[right]);
        }
        else
        {
            return right;
        }
    } while (left < right);
    return right;
}